

		PERECHI
	       ---------

	Fie x(1),x(2),..,x(n) un sir de numere strict pozitive.
	Sa se determine secventa din sirul dat, cu proprietatea ca numarul de perechi
de numere  naturale, nenule (p,q) pentru care suma primelor p numere din secventa este
egala cu suma ultimelor q numere din secventa, este maxima.
	Datele de intrare se vor citi din fisierul text "SIR.TXT" ce contine elementele
sirului, pe o linie, separate printr-un spatiu.
	Datele de iesire vor fi afisate pe ecran sub forma:

	Secventa : x(u),x(u+1),..,x(v)
	(p1,1) (p2,q2) ... (ps,qs)
	Sunt s perechi in secventa [u,v]

unde u,v reprezinta indicii de inceput si sfarsit ale secventei determinate.

EXEMPLU:
	Pt. sirul 2 2 2 3 3 4 6 22 23 iesirea va fi:
	
	Secventa : 2 2 3 3 4
	(2,1) (3,2) (4,3) (5,5)
	Sunt 4 perechi in secventa [2,6].

REZOLVARE:
----------

	Sunt n*(n-1)/2 secvente de testat. Daca, pt. fiecare din secvente, am compara toate
sumele care se obtin cu primele elemente cu toate sumele care se obtin cu ultimele, am ajunge
la o complexitate totala de ordinul n^4; aceasta nu este mai mare doarece, de exemplu, pentru
a afla suma primelor 3 elemente se aduna al treile element la suma primelor doua.
	Este momentul unei observatii care, chiar daca nu intervine direct in rezolvarea pro-
blemei, poate fi utila in rezolvarea multor altor probleme.
	Fie un vector V; cum putem sa aflam, in mod eficient, suma unei secvente de elemente,
situate intre pozitiile i si j? Vom construi de la inceput vectorul sumelor partiale S(i)=
S(i-1)+V(i) pentru i>0. In acest moment, suma elementelor situate intre pozitiile i si j din
V, cu j>i, este data de S(j)-S(i-1).
	Revenind la problema data, se poate realiza o imbunatatire.
	Analiza care urmeaza este realizata in cadrul unei secvente.
	De ce sa comparam toate perechile de sume, daca aceasta nu este necesar?
De exemplu, daca primul element este mai mic decat ultimul, suma ultimelor i elemente nu poate
fi egala cu primul, indiferent de i (este mai mare decat i). Ne reamintim procedeul folosit la
interclasarea a 2 vectori sortati: daca elementul din primul vector este mai mic se avanseaza
in primul vector, in caz contrar in cel de-al doilea.
	Folosim 2 variabile S1 si S2. Acestea vor retine suma primelor, respectiv ultimelor
elemente. Initial, S1 este egal cu primul element, iar S2 cu ultimul. Daca S1=S2 am gasit o
pereche. In acest caz, S1 si S2 "avanseaza" spre capetele opuse ale vectorului si numarul de
perechi creste cu 1. In caz contrar, va "avansa" suma mai mica. Aceasta "avansare" se realizeaza
prin adugarea numarului urmator, pentru S1, sau anterior, pentru S2, care nu a fost luat in con-
siderare.
	Evident, dupa aflarea numarului de perechi acesta este comparat cu optimul si se reali-
zeaza actualizarea daca este cazul.
	Cum justificam aceasta metoda? S1 si S2 parcurg sirurile sumelor primelor, respectiv ul-
timelor elemente, iar aceste siruri sunt ordonate, deoarece elementele care se adauga sunt strict
pozitive.
	Complexitatea este O(n) pentru fiecare secventa, deci O(n^3) pentru ansamblul problemei.